#include"tree.h"

void CreateTree(Tree &T){
	T = NULL;
}

Tnode *CreateTNode (int y){
	Tnode *p= new Tnode;
	if(p == NULL){
		cout <<"not enough memory"<<endl;
		return 0;
	}
	p-> x =y;
	p-> left = NULL;
	p -> right = NULL;
	return p;
}

void AddTNode (Tree &T, int y){
	Tnode *X= CreateTNode (y);
	AddTNode (T, X);
}

void AddTNode (Tree &T, Tnode *X){
	if(T==NULL){
		T = X;
	}
	else{
		if(X->x<T->x)
			AddTNode (T->left,X);
		else if(X->x>T->x)
			AddTNode (T->right,X);
		else cout<<"khong the in duoc";
		
	}
}

void PrintTree(Tree T){
	if(T !=NULL){
		cout<<T->x<<"\t";
		PrintTree(T->left);
		PrintTree(T->right);
	}
}

int SearchKey (Tree T, int key){
	while (T != NULL){
		if(T->x == key){
			return 1;
			break;
		}
		else if(T->x > key) T=T->left;
		else T=T-> right;
	}
	return 0;
}

int CountTNode(Tnode* root){
	if(root== NULL)
		return 0;
	return 1+CountTNode(root->left)+ CountTNode(root->right);
}

void TreeHeight(int count){
	int height = log((double)count)/ log((double)2);
	cout<<"chieu cao cua cay la: "<< height<<endl;
}

int CountLeaf(Tnode* root){
	if (root!=NULL) 
    { 
        if (root->left == NULL && root->right == NULL) 
            return 1;
        return CountLeaf(root->left) + CountLeaf(root->right); 
    } 
    return 0; 
}

int CountLeaf1(Tnode* root){
	if(root==NULL)
		return 0;
	if((root->left == NULL && root->right != NULL)||(root->left != NULL && root->right == NULL))
		return(1+ CountLeaf1(root->left) + CountLeaf1(root->right));
	else return CountLeaf1(root->left) + CountLeaf1(root->right);
}

int CheckPrimeNum(int x){
	for(int i=2; i<= (x/2); i++){
		if(x % i ==0){
			return 0;
			break;}
	}
	return 1;
}

int SumPrimeNum(Tnode * root){
	if( root !=NULL){
		if(CheckPrimeNum(root->x))
			return root->x + SumPrimeNum(root->left)+ SumPrimeNum(root->right);
		return SumPrimeNum(root->left)+ SumPrimeNum(root->right);

	}
	return 0;
}

int CheckSquareNum(int x){
	if (x==int(sqrt((double) x))*int(sqrt( (double)x))) return 1;
	else return 0;
}  

int SumSquareNum(Tnode *root){
	if( root !=NULL){
		if(CheckSquareNum(root->x))
			return root->x + SumSquareNum(root->left)+ SumSquareNum(root->right);
		return SumSquareNum(root->left)+ SumSquareNum(root->right);

	}
	return 0;
}

void DeleteTNode (Tree &T, int key){
	Tnode *p;
	if(T !=NULL){
		if(T-> x < key)
			DeleteTNode(T->right, key);
		else if(T->x > key) DeleteTNode (T->left, key);
		if (T -> x == key ){
			p=T;
			if(T-> left == NULL)
				T=T -> right;
			else {
				if (T -> right == NULL)
					T = T ->left;
				else
					Swap2(p, T-> right);
			}
			delete p;
		}
	}
}






//tien hanh swap doi voi node co 2 node con
void Swap2(Tnode *&p, Tnode *&q){
	if(q->left !=NULL)
		Swap2(p, q->left);
	else {
		p->x=q->x;
		p=q;
		q=q->right;

	}
}
